import java.util.Stack;
//在栈中找最小值，时间复杂度为O（1）
public class MinStack {
    private final Stack<Integer> stack;
    private final Stack<Integer>minStack ;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if(minStack.empty() )  {
            minStack.push(val);
        }else if(!minStack.empty()){
            int ch = minStack.peek();
            if(val <= ch){
                minStack.push(val);
            }

        }
    }

    public void pop() {
        int ch1 = stack.peek();
        int ch2 = minStack.peek();
        if(ch1 == ch2){
            stack.pop();
            minStack.pop();
        }else if(ch1 > ch2){
            stack.pop();
        }

    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        if(!minStack.empty()){
            return minStack.peek();
        }
        return  -1;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */